home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / STREAM13.ARJ / LZWSTREA.ASM < prev    next >
Assembly Source File  |  1992-02-10  |  19KB  |  680 lines
  1. PAGE 60, 132
  2. TITLE 12 bit LZW Compression Scheme
  3. LOCALS @@
  4.  
  5. Comment *
  6.  
  7.   This unit is a modified version of Wilbert van Leijen's LZW unit,
  8.   to implement a stream type that automatically compresses data.
  9.   The original documentation:
  10.  
  11.   This modules implements a 12-bit Lempel-Zev-Welch "crunch" (compress
  12.   data) and "uncrunch" (restore data in its original form) routines.
  13.   InBuffer and OutBuffer are untyped; you must pass pointers to arrays
  14.   (0..MaxRange) of Char or Byte to it, whereby MaxRange is limited to
  15.   2^16-16+1 = 65521 bytes.
  16.  
  17.   You must also supply the size of the input buffer.
  18.  
  19.   The LZW technique is well explained in the following reference:
  20.  
  21.     Terry A. Welch, "A Technique for High Performance Data Compression"
  22.     IEEE Computer
  23.     Vol. 17, no. 6 (June 1984), pp. 8-19
  24.  
  25.   Incorporate these routines as follows in a TP unit:
  26.  
  27.   [ deleted ]
  28.  
  29.   (C) Copyright Wilbert van Leijen, Amsterdam 1990.
  30.   Released to the Public Domain under the condition that this program
  31.   will not be sold for a profit except with written permission from
  32.   the author.
  33.  
  34.   Stream additions (c) copyright D.J. Murdoch, 1991.
  35. *
  36.  
  37. MaxStack   = 4096;                     ; Decompression stack size
  38. TableSize  = MaxStack-1;               ; Upper bound of 12 bit tables
  39. HalfFull   = MaxStack / 2
  40. ProbeValue = 131;                      ; Preferably a prime number
  41. True       = 1
  42. False      = 0
  43. EndList    = -1;                       ; Marks end of a list
  44. NoPrev     = -2;                       ; Code for no previous character
  45. Empty      = -3;                       ; Indicates empty
  46.  
  47. DataSize   = [BP+18]                   ; Number of bytes input
  48. OutputSize = word ptr [BP+16]          ; Max number to output
  49. InputBuf   = [BP+12]                   ; Input data buffer
  50. OutputBuf  = [BP+8]                    ; Output data buffer
  51. Tables     = [BP+4]                    ; Where the tables are
  52.  
  53. Table      STRUC
  54.  
  55. Collision  DB      MaxStack DUP(?)     ; Hash table entries
  56. PrefixTable DW     MaxStack DUP(?)     ; Code for preceding stringf
  57. SuffixTable DB     MaxStack DUP(?)     ; Code for current character
  58. ChildTable DW      MaxStack DUP(?)     ; Next duplicate in collision list
  59. CharStack  DB      MaxStack DUP(?)     ; Decompression stack
  60. StackPtr   DW      ?                   ; Decompression stack depth
  61. Prefix     DW      ?                   ; Previous code string
  62. TableUsed  DW      ?                   ; # string table entries used
  63. InputPos   DW      ?                   ; Index in input buffer
  64. OutputPos  DW      ?                   ; Index in output buffer
  65. LastHit    DW      ?                   ; Last empty slot in collision table
  66. CodeBuf    DW      ?                   ; Temporary code buffer
  67.  
  68. SaveIP     DW      ?                   ; Saved registers between calls
  69. SaveAX     DW      ?
  70. SaveCX     DW      ?
  71. SaveDX     DW      ?
  72.  
  73. NotFound   DB      ?                   ; Character combination found flag
  74.  
  75. Table      ENDS
  76.  
  77. ;  CH register is set aside for final output character (= Suffix)
  78.  
  79. Code       SEGMENT Word Public
  80.            ASSUME  CS:Code
  81.  
  82.            Public  Initialise
  83.            Public  PutSignature
  84.            Public  Crunch
  85.            Public  FlushLZW
  86.            Public  GetSignature
  87.            Public  Uncrunch
  88.  
  89. ;  Initialise variables, fill tables
  90.  
  91. Initialise PROC    near
  92.  
  93.            PUSH    BP
  94.            MOV     BP,SP
  95.            PUSH    DS               ; save DS
  96.            LDS     BX,Tables        ; get DS:BX to point to the tables
  97.  
  98.            XOR     AX, AX
  99.            MOV     [BX].InputPos, AX
  100.            MOV     [BX].OutputPos, AX
  101.            MOV     [BX].TableUsed, AX
  102.            MOV     [BX].StackPtr, AX
  103.            MOV     [BX].CodeBuf, Empty
  104.  
  105. ;  Loop:
  106. ;    Clear collision table
  107. ;    Set prefix to 'no previous character' code
  108. ;    Set child nodes to 'end of list' code
  109.  
  110.            MOV     DX, Tablesize
  111. @@1:       MOV     DI, DX
  112.            MOV     [BX+DI+Collision], 0
  113.            SHL     DI, 1
  114.            MOV     [BX+DI+PrefixTable], NoPrev
  115.            MOV     [BX+DI+ChildTable], EndList
  116.            DEC     DX
  117.            JNS     @@1
  118.  
  119. ;  Loop:
  120. ;   Enter all single characters into the hash table
  121.  
  122.            MOV     DX, 255
  123.            MOV     [BX].Prefix, NoPrev
  124. @@2:       MOV     CH, DL
  125.            CALL    MakeEntry
  126.            DEC     DX
  127.            JNS     @@2
  128.  
  129.            MOV     [BX].SaveCX,CX
  130.            POP     DS
  131.            POP     BP
  132.            RETN    4
  133. Initialise ENDP
  134.  
  135. ;  Hash function:  'fold' number
  136. ;    AX := (Prefix shl 5 xor Suffix) and TableSize
  137. ;    uses CL,DX
  138.  
  139. HashNumber MACRO
  140.            XOR     DX, DX
  141.            MOV     DL, CH
  142.            MOV     AX, [BX].Prefix
  143.            MOV     CL, 5
  144.            SHL     AX, CL
  145.            XOR     AX, DX
  146.            AND     AX, TableSize
  147.            ENDM
  148.  
  149. ;  Store a character combination in the hash table
  150.  
  151. MakeEntry  PROC    Near
  152.            PUSH    DX
  153.            HashNumber
  154.  
  155. ;  Rehash is necessary if entry in the hash table is occupied
  156.  
  157.            MOV     DI, AX
  158.            CMP     [BX+DI+Collision], False
  159.            JE      @@6
  160.  
  161. ;  Loop:
  162. ;    Advance index of ChildTable to last empty list
  163.  
  164. @@1:       MOV     DI, AX
  165.            SHL     DI, 1
  166.            CMP     [BX+DI+ChildTable], EndList
  167.            JE      @@2
  168.            MOV     AX, [BX+DI+ChildTable]
  169.            JMP     Short @@1
  170.  
  171. ;  If the hash table is less than 50% loaded
  172. ;    Increase index with the probing value
  173.  
  174. @@2:       CMP     [BX].TableUsed, HalfFull
  175.            JAE     @@3
  176.            MOV     SI, AX
  177.            ADD     SI, ProbeValue
  178.            AND     SI, TableSize
  179.            JMP     Short @@4
  180.  
  181. ;  Else deal with the clustering problem
  182. ;  A simple yet effective solution is to start probing at the
  183. ;  empty slot of the hash table found during the previous run
  184.  
  185. @@3:       MOV     SI, [BX].LastHit
  186.  
  187. ;  Loop:
  188. ;    Probe hash table until an empty slot is found
  189.  
  190. @@4:       CMP     [BX+SI+Collision], False
  191.            JE      @@5
  192.            INC     SI
  193.            AND     SI, TableSize
  194.            JMP     Short @@4
  195.  
  196. ;  Found an empty slot, save index in ChildTable
  197. ;  Store index in LastHit
  198.  
  199. @@5:       MOV     DI, AX
  200.            SHL     DI, 1
  201.            MOV     [BX+DI+ChildTable], SI
  202.            MOV     DI, SI
  203.            MOV     [BX].LastHit, SI
  204.  
  205. ;  Return:
  206. ;    Indicate hash table slot's been occupied
  207. ;    Store character combination in PrefixTable, SuffixTable
  208. ;    Indicate 'end of list' in ChildTable
  209. ;    Bump table load counter
  210.  
  211. @@6:       MOV     [BX+DI+Collision], True
  212.            MOV     [BX+DI+SuffixTable], CH
  213.            SHL     DI, 1
  214.            MOV     [BX+DI+ChildTable], EndList
  215.            MOV     AX, [BX].Prefix
  216.            MOV     [BX+DI+PrefixTable], AX
  217.            INC     [BX].TableUsed
  218.            POP     DX
  219.            RETN
  220. MakeEntry  ENDP
  221.  
  222. ;  Lookup a character combination in the hash table
  223.  
  224. LookupStr  PROC    Near
  225.            HashNumber
  226.            XCHG    SI, AX
  227.  
  228. ;  Search through list of hash collision entries for one that match
  229. ;  Loop
  230. ;    Entry is found if prefix and suffix match
  231. ;    If no match, advance index to entry in ChildTable
  232. ;  Until entry is found or no such list exists in ChildTable
  233.  
  234. @@1:       MOV     DI, SI
  235.            MOV     AL, [BX+DI+SuffixTable]
  236.            CMP     AL, CH
  237.            JNE     @@2
  238.            SHL     DI, 1
  239.            MOV     AX, [BX+DI+PrefixTable]
  240.            CMP     AX, [BX].Prefix
  241.            JE      @@3
  242.  
  243. @@2:       MOV     DI, SI
  244.            SHL     DI, 1
  245.            MOV     SI, [BX+DI+ChildTable]
  246.            CMP     SI, EndList
  247.            JNE     @@1
  248.  
  249. ;  Return index from ChildTable in AX
  250.  
  251. @@3:       XCHG    AX, SI
  252.            RETN
  253. LookupStr  ENDP
  254.  
  255. ;  Retrieve next character from the input buffer
  256.  
  257. GetChar    MACRO
  258.            LES     DI, InputBuf
  259.            ADD     DI, [BX].InputPos
  260.            MOV     AL, ES:[DI]
  261.            INC     [BX].InputPos
  262.            ENDM
  263.  
  264. ;  Store next character in AL into the output buffer
  265.  
  266. PutChar    MACRO
  267.            LES     DI, OutputBuf
  268.            ADD     DI, [BX].OutputPos
  269.            STOSB
  270.            INC     [BX].OutputPos
  271.            ENDM
  272.  
  273. ;  Retrieve compressed code from input buffer
  274.  
  275. GetCode    PROC    Near
  276.  
  277.            MOV     SI, [BX].CodeBuf
  278. ;  Get first character and store it in a temporary buffer
  279.  
  280.            GetChar
  281.            XOR     AH, AH
  282.            MOV     DX, AX
  283.  
  284. ;  If input code is empty
  285.  
  286.            CMP     SI, Empty
  287.            JNE     @@1
  288.  
  289. ;    Get next character
  290. ;    Return 8 bits from first character + 4 bits from second character
  291. ;    Save the remaining 4 bits of the second character for next time
  292.  
  293.            GetChar
  294.            MOV     SI, AX
  295.            MOV     CL, 4
  296.            SHR     AX, CL
  297.            MOV     DI, AX
  298.            MOV     AX, DX
  299.            SHL     AX, CL
  300.            ADD     AX, DI
  301.            JMP     @@2
  302.  
  303. ;  Else
  304. ;    Get the last 4 bits from the input code + 8 bits from the second char
  305.  
  306. @@1:       MOV     AX, SI
  307.            XCHG    AH, AL
  308.            AND     AH, 0Fh
  309.            ADD     AX, DX
  310.            MOV     SI, Empty
  311. @@2:
  312.            MOV     [BX].CodeBuf,SI
  313.            RETN
  314. GetCode    ENDP
  315.  
  316. ;  Store compressed code in the output buffer
  317.  
  318. PutCode    PROC    Near
  319.            MOV     DI, [BX].CodeBuf
  320.            MOV     DX, [BX].Prefix
  321.  
  322. ;  If output code is empty
  323.  
  324.            CMP     DI, Empty
  325.            JNE     @@1
  326.  
  327. ;    Store first 8 bits in the output buffer
  328. ;    Save last 4 bits for the next time through
  329.  
  330.            MOV     AX, DX
  331.            MOV     CL, 4
  332.            SHR     AX, CL
  333.            PutChar
  334.            MOV     DI, DX
  335.            JMP     @@2
  336.  
  337. ;  Else
  338. ;    Put out last 4 bits of previous code + first 4 bits of this code
  339. ;    Next, put out last 8 bits of this code
  340. ;    Indicate output code as empty
  341.  
  342. @@1:       MOV     AX, DI
  343.            MOV     CL, 4
  344.            SHL     AX, CL
  345.            ADD     AL, DH
  346.            PutChar
  347.            MOV     AL, DL
  348.            PutChar
  349.            MOV     DI, Empty
  350. @@2:       MOV     [BX].CodeBuf,DI
  351.            RETN
  352. PutCode    ENDP
  353.  
  354. ;  Start the compressor by putting 'LZ'
  355.  
  356. PutSignature PROC  Near
  357.            PUSH    BP
  358.            MOV     BP,SP
  359.            PUSH    DS               ; save DS
  360.            LDS     BX,Tables        ; get DS:BX to point to the tables
  361.  
  362.            MOV     [BX].OutputPos, 0
  363.  
  364. ;  Get first character and store it in Suffix
  365. ;  There are no character combinations yet
  366.  
  367.            MOV     AL, 'L'
  368.            MOV     CH, AL
  369.            MOV     [BX].Prefix, NoPrev
  370.            CALL    LookupStr
  371.            MOV     [BX].Prefix, AX
  372.  
  373. ;  Get next character
  374.  
  375.            MOV     AL, 'Z'
  376.            MOV     CH, AL
  377.  
  378.            MOV     [BX].SaveCX,CX
  379.  
  380.            MOV     AL,True          ;  Return success
  381.            POP     DS
  382.            POP     BP
  383.            RET     4
  384. PutSignature ENDP
  385.  
  386.  
  387. Crunch     PROC    Near
  388.            PUSH    BP
  389.            MOV     BP,SP
  390.            PUSH    DS               ; save DS
  391.            LDS     BX,Tables        ; get DS:BX to point to the tables
  392.            MOV     CX,[BX].SaveCX   ; get saved registers
  393.            MOV     [BX].InputPos, 0
  394.            MOV     [BX].OutputPos, 0
  395.            DEC     OutputSize       ; sometimes we write 2 bytes per loop,
  396.                                     ; so reduce this for safety
  397.  
  398. ;  Loop:
  399. ;    Process all characters from input buffer
  400.  
  401. @@1:       MOV     DX, [BX].InputPos
  402.            MOV     AX, [BX].OutputPos
  403.            CMP     DX, DataSize
  404.            JAE     @@5
  405.            CMP     AX, OutputSize
  406.            JAE     @@5
  407.  
  408. ;  Lookup the character combination
  409. ;  Store if not found and if empty slots are available in the hash table
  410.  
  411.            CALL    LookupStr
  412.            MOV     DI, AX
  413.            CMP     DI, EndList
  414.            JNE     @@3
  415.            PUSH    DI
  416.            CMP     [BX].TableUsed, TableSize
  417.            JA      @@2
  418.            CALL    MakeEntry
  419.  
  420. ;  Store code in the output buffer
  421. ;  If string is in table, keep looking for longer strings
  422.  
  423. @@2:       CALL    PutCode
  424.            POP     DI
  425.            MOV     [BX].Prefix, NoPrev
  426.            XCHG    DX, DI
  427.            CALL    LookupStr
  428.            XCHG    DI, DX
  429.            MOV     [BX].Prefix, AX
  430.            JMP     Short @@4
  431.  
  432. ;  Get next character
  433.  
  434. @@3:       MOV     [BX].Prefix, DI
  435. @@4:       GetChar
  436.            MOV     CH, AL
  437.            JMP     Short @@1
  438.  
  439. @@5:       MOV     [BX].SaveCX,CX
  440.            ; return number written in AX
  441.            ; and number used in DX
  442.            POP     DS
  443.            POP     BP
  444.            RET     14
  445. Crunch     ENDP
  446.  
  447. ;  Make sure the last code will be written out
  448. ;  If the output code <> Empty, store the last 4 pending bits
  449.  
  450. FlushLZW   Proc    Near
  451.            PUSH    BP
  452.            MOV     BP,SP
  453.            PUSH    DS               ; save DS
  454.            LDS     BX,Tables        ; get DS:BX to point to the tables
  455.            MOV     CX,[BX].SaveCX   ; get saved registers
  456.            MOV     [BX].InputPos, 0
  457.            MOV     [BX].OutputPos, 0
  458. @@5:       CALL    PutCode
  459.            MOV     SI,[BX].CodeBuf
  460.            CMP     SI, Empty
  461.            JE      @@7
  462.            MOV     AX, SI
  463.            MOV     CL, 4
  464.            SHL     AX, CL
  465.            PutChar
  466.  
  467. ;  Return the number of bytes written to the output buffer
  468.  
  469. @@7:       MOV     AX, [BX].OutputPos
  470.            MOV     [BX].SaveCX,CX
  471.            POP     DS
  472.            POP     BP
  473.            RET     8
  474. FlushLZW   ENDP
  475.  
  476. ;  Run through code extracting single characters from code string until
  477. ;  no more characters can be removed.  Push these onto the stack.
  478. ;  They will be entered in reverse order, and will come out in forwards order
  479. ;  when popped off
  480.  
  481. PushChar   PROC    Near
  482. @@1:       MOV     DI, SI
  483.            SHL     DI, 1
  484.            CMP     [BX+DI+PrefixTable], NoPrev
  485.            JNE     @@2
  486.            RETN
  487.  
  488. @@2:       MOV     AL, [BX+SI+SuffixTable]
  489.            INC     [BX].StackPtr
  490.            MOV     DI, [BX].StackPtr
  491.            MOV     [BX+DI+CharStack], AL
  492.            SHL     SI, 1
  493.            MOV     SI, [BX+SI+PrefixTable]
  494.            JMP     Short @@1
  495. PushChar   ENDP
  496.  
  497. ;  While StackPtr > 0
  498. ;    Pop a character from the stack
  499.  
  500. PopChar    PROC    Near
  501.            PutChar
  502.            MOV     DI, [BX].StackPtr
  503.            OR      DI, DI
  504.            JE      @@1
  505.            MOV     AL, [BX+DI+CharStack]
  506.            DEC     [BX].StackPtr
  507.            RETN
  508.  
  509. @@1:       MOV     AX, Empty
  510.            RETN
  511. PopChar    ENDP
  512.  
  513. ; Check for correct start of buffer, and initialize registers
  514.  
  515. GetSignature PROC  Near
  516.            PUSH    BP
  517.            MOV     BP, SP
  518.            PUSH    DS               ; save DS
  519.            LDS     BX,Tables        ; get DS:BX to point to the tables
  520.  
  521. ;  Get first string and check the corresponding character
  522. ;  Keep a copy of this code
  523.  
  524.            CALL    GetCode
  525.            MOV     [BX].Prefix, AX
  526.            MOV     SI, AX
  527.            MOV     CH, [BX+SI+SuffixTable]
  528.            CMP     CH, 'L'
  529.            JNE     @@2
  530.  
  531.            CALL    GetCode
  532.            MOV     [BX].SaveDX, AX
  533.  
  534. ;  Do half a run through the old Uncrunch loop
  535.  
  536. ;         (  skip size check )
  537.  
  538.            MOV     [BX].Notfound, False
  539.            MOV     SI, AX
  540.  
  541. ;         (  skip collision test, & PushChar call  )
  542.  
  543.            MOV     CH, [BX+SI+SuffixTable]
  544.            CMP     CH, 'Z'
  545.            JNE     @@2
  546.  
  547. ;         (  do PopChar's MOV AX, Empty )
  548.            MOV     [BX].SaveAX,Empty
  549.  
  550.            MOV     AL,True     ; Success!  We're ready for the loop.
  551.            JMP     @@1
  552.  
  553. @@2:       MOV     AL,False    ; It failed!
  554.  
  555. @@1:       MOV     [BX].SaveCX,CX
  556.            MOV     [BX].SaveIP,OFFSET MainLoop
  557.            POP     DS
  558.            POP     BP
  559.            RET     14
  560. GetSignature ENDP
  561.  
  562.  
  563. UnCrunch   PROC    Near
  564.            PUSH    BP
  565.            MOV     BP,SP
  566.            PUSH    DS               ; save DS
  567.            LDS     BX,Tables        ; get DS:BX to point to the tables
  568.            MOV     AX,[BX].SaveAX   ; get saved registers
  569.            MOV     CX,[BX].SaveCX
  570.            MOV     DX,[BX].SaveDX
  571.  
  572.            MOV     [BX].InputPos, 0 ; set up string pointers & sizes
  573.            MOV     [BX].OutputPos, 0
  574.            DEC     Word Ptr DataSize         ; sometimes we need to read two
  575.            JMP     [BX].SaveIP
  576.  
  577. ;  Loop:
  578. ;    Process all characters from input buffer
  579.  
  580. ;  While the stack is not empty, remove and output all characters from
  581. ;  stack which are rest of characters in the string
  582.  
  583. @@1:       MOV     DI,[BX].OutputPos ; Check if there's room for more characters
  584.            CMP     DI,OutputSize
  585.            JB      @@3
  586.            CALL    ExitLoop          ; Exit from Uncrunch
  587.  
  588. Mainloop:
  589. @@3:       CMP     AX, Empty
  590.            JE      @@4
  591.            CALL    PopChar
  592.            JMP     Short @@1
  593.  
  594. ;  If code isn't known, store the follower character of last
  595. ;  character of string
  596.  
  597. @@4:       CMP     [BX].NotFound, False
  598.            JE      @@5
  599.            PUSH    AX
  600.            MOV     AL, CL
  601.            MOV     CH, AL
  602.            PutChar
  603.            POP     AX
  604.  
  605. ;  Check whether there's enough space for another char
  606.  
  607. @@8:       MOV     DI,[BX].OutputPos
  608.            CMP     DI,OutputSize
  609.            JB      @@5
  610.  
  611. ;  No space, so quit
  612.  
  613.            CALL    ExitLoop
  614.  
  615. ;  If the hash table is not full
  616. ;    Enter code into table
  617. ;  Make current code the previous code
  618. ;  Get next code
  619.  
  620. @@5:       CMP     [BX].TableUsed, TableSize
  621.            JA      @@6
  622.            CALL    MakeEntry
  623. @@6:       MOV     [BX].Prefix, DX
  624.            CALL    GetCode
  625.            XCHG    DX, AX
  626.  
  627. ; Old top of loop
  628.  
  629.            MOV     AX, [BX].InputPos
  630.            CMP     AX, DataSize
  631.            JB      @@10
  632.  
  633. ;  Out of data, so exit
  634.  
  635.            CALL    ExitLoop
  636.  
  637. ;  Retrieve character from string
  638. ;  Keep a copy of it in CL
  639.  
  640. @@10:      MOV     [BX].NotFound, False
  641.            MOV     SI, DX
  642.            CMP     [BX+SI+Collision], False
  643.            JNE     @@2
  644.            MOV     AL, CH
  645.            MOV     CL, AL
  646.            MOV     SI, [BX].Prefix
  647.            MOV     [BX].NotFound, True
  648.  
  649. ;  Get first character from string
  650.  
  651. @@2:       CALL    PushChar
  652.            MOV     AL, [BX+SI+SuffixTable]
  653.            MOV     CH, AL
  654.            CALL    PopChar
  655.  
  656.            JMP     @@1
  657.  
  658. UnCrunch   ENDP
  659.  
  660. ExitLoop   PROC    Near             ; allows exit from UnCrunch loop
  661.                                     ; and resumption at several places.
  662.            POP     [BX].SaveIP      ; Get address
  663.            MOV     [BX].SaveAX,AX   ; Save registers
  664.            MOV     [BX].SaveCX,CX
  665.            MOV     [BX].SaveDX,DX
  666.  
  667. ;  Return the number of bytes written to the output buffer in AX
  668. ;  and the number of bytes used in DX
  669.  
  670.            MOV     AX, [BX].OutputPos
  671.            MOV     DX, [BX].InputPos
  672.  
  673.            POP     DS
  674.            POP     BP
  675.            RETN    14
  676. ExitLoop   ENDP
  677.  
  678. Code       ENDS
  679.            END
  680.